import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {
    public static int halveArray(int[] nums) {
        int count = 0;//操作的次数
        int subSum = 0;//需要减去的数的和
        double sum = 0;//nums的元素总和
        int len = nums.length;//数组长度

        double[] arr = new double[len];
        for (int i = 0; i < len; i++) {
            arr[i] = nums[i];
        }
        for (double num : arr) {
            sum += num;
        }

        while (subSum < sum / 2) {
            Arrays.sort(arr);
            subSum += arr[len - 1] / 2;
            System.out.println(subSum);
            arr[len - 1] /= 2;
            count++;
            System.out.println(Arrays.toString(arr));
        }
        return count;
    }

    public int halveArray2(int[] nums) {
        int count = 0;//操作的次数
        double subSum = 0;//需要减去的数的和
        double sum = 0;//nums的元素总和
        int len = nums.length;//数组长度

        PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));//创建大根堆

        for (double num : nums) {
            heap.offer(num);
            sum += num;
        }

        while (subSum < sum / 2) {
            double num = heap.poll();
            subSum += num / 2;
            heap.offer(num / 2);
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(halveArray(new int[]{32,98,23,14,67,40,26,9,96,96,91,76,4,40,42,2,31,13,16,37,62,2,27,25,100,94,14,3,48,56,64,59,33,10,74,47,73,72,89,69,15,79,22,18,53,62,20,9,76,64}));
    }
}
